package com.cqs.leetcode;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.*;

/**
 *
 *
 * DFS算法:
 * 有向环检测
 *
 * 数据: int[] nums ---> 不包含0
 *
 * 注意点：
 * 1.The loop must be "forward" or "backward'.表示环只能有个一方向
 * 所以[2,3,1,-2]不构成环 因为存在两个方向 -->数组全部是整数或者全部是负数
 *
 * 2.注意自己指向自己不算 比如 [1], [3,1]
 *
 * 3.注意要将其看成环数组 所以 [3,1] 等价于 [1,1]
 *
 * 4.构成环不一定要从第一个元素开始 所以[1,1,2] 存在符合条件的环
 *
 *
 *
 * Created by cqs on 2018/5/4.
 */
public class CircularArrayLoop {


    public boolean circularArrayLoop(int[] nums) {
        if (nums == null || nums.length < 2) return false;
        //DFS
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.clear();
            int index = i;
            int sign = getSign(nums[index]);
            set.add(index);
            while (true) {
                int oldIndex = index;
                index = (nums[index] + index + nums.length) % nums.length;
                if (index == oldIndex) break;
                sign *= getSign(nums[index]);
                if (sign < 0) break;//相同方向
                if (set.contains(index))return true;
                set.add(index);
            }
        }
        return false;
    }

    private int getSign(int num) {
        return num > 0 ? 1 : -1;
    }

    public static void main(String[] args) {
        CircularArrayLoop loop = new CircularArrayLoop();
//        int[] a = {-2, 1, -1, -2, -2};
        int[] a = {1, 1, 1, 2};
        ArraysUtils.print(a);
        boolean b3 = loop.circularArrayLoop(a);
        System.out.println( b3);
    }
}
